<!--
 * @Author: your name
 * @Date: 2021-07-22 13:37:13
 * @LastEditTime: 2021-07-24 16:19:31
 * @Description: 
-->
<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>二叉搜索树结构</title>
</head>

<body>
  <p>比较好的二叉搜索树数据应该是左右均匀</p>
  <p>但是插入连续数据后，分布得不均匀，称为非平衡树</p>
  <p>对应一棵非平衡二叉树，相当于编写了一个链表</p>

  <script>
    function BinarySearchTree() {
      function Node(key) {
        this.key = key
        this.left = null
        this.right = null
      }

      // 属性
      this.root = null

      // 插入数据
      BinarySearchTree.prototype.insert = function (key) {
        // 1. 根据key创建节点
        var newNode = new Node(key)

        // 2. 判断根节点是否有值
        if (this.root === null) {
          this.root = newNode
        } else {
          this.insertNode(this.root, newNode)
        }
      }

      // 递归查找插入的位置
      BinarySearchTree.prototype.insertNode = function (node, newNode) {
        if (newNode.key < node.key) { // 向左查找
          if (node.left == null) {
            node.left = newNode
          } else {
            this.insertNode(node.left, newNode)
          }
        } else { // 向右查找
          if (node.right == null) {
            node.right = newNode
          } else {
            this.insertNode(node.right, newNode)
          }
        }
      }

      // 树的遍历
      // 1. 先序遍历（先遍历左节点再遍历右节点）
      BinarySearchTree.prototype.preOrderTraversal = function (handler) {
        this.preOrderTraversalNode(this.root, handler)
      }

      BinarySearchTree.prototype.preOrderTraversalNode = function (node, handler) {
        if (node !== null) {
          // 1. 处理经过的节点
          handler(node.key)

          // 2. 处理经过节点的左子节点
          this.preOrderTraversalNode(node.left, handler)

          // 3. 处理经过节点的右子节点
          this.preOrderTraversalNode(node.right, handler)
        }
      }

      // 2. 中序遍历：中序遍历其左子树；访问根节点；中序遍历其右子树

      BinarySearchTree.prototype.midOrderTraversal = function (handler) {
        this.midOrderTraversalNode(this.root, handler)
      }

      BinarySearchTree.prototype.midOrderTraversalNode = function (node, handler) {
        if (node !== null) {
          // 1. 处理左子树中的节点
          this.midOrderTraversalNode(node.left, handler)

          // 2. 处理节点
          handler(node.key)

          // 3. 处理右子树中的节点
          this.midOrderTraversalNode(node.right, handler)
        }
      }

      // 3. 后序遍历：后序遍历其左子树；后序遍历其右子树；访问根节点
      BinarySearchTree.prototype.postOrderTraversal = function (handler) {
        this.postOrderTraversalNode(this.root, handler)
      }

      BinarySearchTree.prototype.postOrderTraversalNode = function (node, handler) {
        if (node !== null) {
          // 1. 处理左树中的节点
          this.postOrderTraversalNode(node.left, handler)

          // 2. 处理右子树中的节点
          this.postOrderTraversalNode(node.right, handler)

          // 3. 处理节点
          handler(node.key)
        }
      }

      // 寻找最大值
      BinarySearchTree.prototype.max = function () {
        // 1. 获取根节点
        var node = this.root

        // 2. 依次向右不断的查找，直到节点为null
        var key = null
        while (node !== null) {
          key = node.key
          node = node.right
        }

        return key
      }

      // 寻找最小值
      BinarySearchTree.prototype.min = function () {
        // 1. 获取根节点
        var node = this.root

        // 2. 依次向左不断的查找，直到节点为null
        var key = null
        while (node !== null) {
          key = node.key
          node = node.left
        }

        return key
      }

      // 搜索特定的key
      BinarySearchTree.prototype.search = function (key) {
        // 1. 获取根节点
        var node = this.root

        // 2. 循环搜索key
        while (node !== null) {
          if (key < node.key) {
            node = node.left
          } else if (key > node.key) {
            node = node.right
          } else {
            return true
          }
        }

        return false
      }

      // 删除节点
      BinarySearchTree.prototype.remove = function (key) {
        // 1. 查找到要删除的节点
        // 1.1 定义变量，保存一些信息
        var current = this.root
        var parent = null
        var isLeftChild = true

        // 1.2 开始寻找删除的节点
        while (current.key !== key) {
          parent = current
          if (key < current.key) {
            isLeftChild = true
            current = current.left
          } else {
            isLeftChild = false
            current = current.right
          }

          // 已经找到最后节点依然没有找到current.key === key
          if (current === null) return false
        }

        // 2. 根据对应情况删除节点
        // 2.1 删除的是叶子节点(没有子节点)
        if (current.left === null && current.right === null) {
          if (current == this.root) { // 刪除的是根节点并且根节点是叶子节点
            this.root = null
          } else if (isLeftChild) {
            parent.left = null
          } else {
            parent.right = null
          }
        }

        // 2.2 删除的节点有一个子节点
        else if (current.right === null) {
          if (current == this.root) {
            this.root = current.left
          } else if (isLeftChild) {
            parent.left = current.left
          } else {
            parent.right = current.left
          }
        } else if (current.left === null) {
          if (current == this.root) {
            this.root = current.right
          } else if (isLeftChild) {
            parent.left = current.right
          } else {
            parent.right = current.right
          }
        }
        // 2.3 删除的节点有两个子节点；从子树找大小比较接近的替换被删除的位置（左子树的最大值或右子树的最小值）
        // 前驱：比current小一点点的节点；后继：比current大一点点的节点
        else {
          // 1. 获取后继节点
          var successor = this.getSuccssor(current)

          // 2. 判断是否根节点
          if (current == this.root) {
            this.root = successor
          } else if (isLeftChild) {
            parent.left = successor
          } else {
            parent.right = successor
          }

          // 3. 将删除节点的左子树 = current.left
          successor.left = current.left

        }

      }

      // 找后继的方法
      BinarySearchTree.prototype.getSuccssor = function (delNode) {
        // 1. 定义变量，保存找到的后继
        var successor = delNode
        var current = delNode.right
        var successorParent = delNode

        // 2. 循环查找
        while (current != null) {
          successorParent = successor
          successor = current
          current = current.left
        }

        // 3. 判断寻找的后继节点是否直接就是delNode的right节点
        if (successor != delNode.right) {
          successorParent.left = successor.right
          successor.right = delNode.right
        }

        return successor
      }
    }

    var b = new BinarySearchTree()

    b.insert(11)
    b.insert(7)
    b.insert(15)
    b.insert(5)
    b.insert(3)
    b.insert(9)
    b.insert(8)
    b.insert(10)
    b.insert(13)
    b.insert(12)
    b.insert(14)
    b.insert(20)
    b.insert(18)
    b.insert(25)
    b.insert(6)

    // var str = ''
    // b.preOrderTraversal(function (key) {
    //   str += key + ' '
    // })
    // console.log(str)

    // var mid = ''
    // b.midOrderTraversal(function (key) {
    //   mid += key + ' '
    // })
    // console.log(mid)

    // console.log(b.max())
    // console.log(b.min())
    // console.log(b.search(6))

    b.remove(9)
    b.remove(7)
    b.remove(15)

    var str = ''
    b.postOrderTraversal(function (key) {
      str += key + ' '
    })
    console.log(str)
  </script>
</body>

</html>